package com.sjc.algorithm.sort;

import java.util.Arrays;

/**
 * 快速排序  双边循环法
 * @author by SangJiacun
 * @Date 2020/5/11 18:26
 */
public class DoubleCycleSort {

    public static void main(String[] args) {
        int[] arr = new int[]{4,4,6,5,3,2,8,1};
        quickSort(arr,0,arr.length-1);
        System.out.println(Arrays.toString(arr));

    }

    /**
     * 快速排序
     * @param arr 待排序的数组
     * @param start 开始位置
     * @param end 结束位置
     */
    private static void quickSort(int[] arr,int start,int end){
        // 递归结束条件：start >= end
        if(start >= end){
            return;
        }
        // 得到基准元素 位置
        int pivot = partition(arr, start, end);
        // 根据基准元素，分成两部分进行递归排序
        quickSort(arr,start,pivot-1);
        quickSort(arr,pivot+1,end);
    }

    /**
     * 得到 基准点，
     * 基准点的左边的所有值 小于基准点，
     * 基准点的右边的所有值 大于基准点
     * @param arr  待排序数组
     * @param start 开始位置
     * @param end 结束位置
     * @return left指针和right指针重合的索引位置
     */
    private static int partition(int[] arr,int start,int end){
        // 取第1个位置 的元素 作为基准元素
        int pivot = arr[start];
        int left = start;
        int right = end;

        while(left != right ){
            // 如果right指针的值 大于 基准点，左移
            while(left < right && arr[right] > pivot){
                right--;
            }

            // 如果left指针的值 小于等于 基准点，右移
            while(left < right && arr[left] <= pivot){
                left++;
            }

            //此时，right指针的值 小于基准点，left指针的值 大于基准点，交换两个指针的值
            if(left < right){
                int temp = arr[right];
                arr[right] = arr[left];
                arr[left] = temp;
            }
        }
        // 现在left指针 和 right指针重合，重合的位置的值要和基准点的值 交换
        // 本快速排序的基准点是每段的start位置的值，即 pivot = arr[start];
        arr[start] = arr[left];
        arr[left] = pivot;
        return left;
    }
}
